깊이 우선 탐색(DFS)

Node에서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다
자기 자신을 호출하는 재귀(Recursion)의 형태를 가지고 있다

단순 검색 속도 자체는 너비 우선 탐색(BFS)보다 느리다

맹목적 탐색 방법의 하나로, 탐색 트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준의 한 개의 자식 노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지의 자식 노드의 첨가 과정을 반복해 가는 방식이다.

깊이 제한과 백트래킹

탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 깊이 제한을 사용한다. 깊이 제한에 도달할 때까지 목표 노드가 발견되지 않으면 최근에 첨가된 노드의 부모노드로 되돌아와서, 부모노드에 이전과는 다른 동작자를 적용하여 새로운 자식노드를 생성한다.

여기서 부모노드로 되돌아오는 과정을 백트래킹이라고 한다.

장점

단지 현 경로상의 노드들만을 기억하면 되므로 저장 공간의 수요가 비교적 적다
목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다

단점

해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다.

얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이 우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

구현 핵심

재귀, Stack
방문 처리 배열 visited
방문한 노드를 저장하는 배열 ArrayList
탐색을 종료하는 조건

DFS 알고리즘 탐색 과정